package algorithms.sort;

/**
 * 三向切分的快速排序
 * @author glogo
 *
 */
public class QuickSort3 {

	public static void sort(Comparable[] a){
		sort(a, 0, a.length - 1);
	}
	
	private static void sort(Comparable[] a, int lo, int hi){
		if(hi <=lo) return;
		int lt = lo, i = lo + 1, gt = hi;
		Comparable v = a[lo];	//这里可以取三个分组中的平均数再平均数
		while(i <= gt){
			int cmp = a[i].compareTo(v);
			if(cmp < 0)	exch(a, lt++, i++);
			else if(cmp > 0)	exch(a, i, gt++);
			else	i++;
		}
		sort(a, lo, lt - 1);
		sort(a, gt + 1, hi);
	}
	
	private static boolean less(Comparable v, Comparable w){
		return v.compareTo(w) < 0;
	}
	
	private static void exch(Comparable[] a, int i, int j){
		Comparable t = a[i];
		a[i] = a[j];
		a[j] = t;
	}

	public static void show(Comparable[] a){
		for(int i = 0; i < a.length; i++){
			System.out.print(a[i] + " ");
		}
		System.out.println();
	}
	
	public static void main(String[] args) {
		String a[]={"4","4","7","8","6","3","4","4","4","4","4","2","5","9","4","2"};
		long m = System.currentTimeMillis();
		QuickSort.sort(a);
		System.out.println(System.currentTimeMillis() - m);
		QuickSort.show(a);
	}

}
